package com.zlk.algorithm.algorithm.dynamicPlan;

// 环绕字符串中唯一的子字符串
// 定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串
// 所以 base 看起来是这样的：
// "..zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd.."
// 给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现
// 测试链接 : https://leetcode.cn/problems/unique-substrings-in-wraparound-string/
public class Code07_UniqueSubstringsWraparoundString {


    //思路：
    // 1、此题不能根据位置动态规划，要根据字符动态规划
    // 2、dp含义 就是以当前字符结尾的往前相邻的最大 长度，然后累加和就是答案
    //    为啥累加和就是答案如下
    //    a b c     dp【a】 =1 (a)  dp【b】=2 (b,ab)  dp【c】=3 (c ,bc,abc)
    //
    // 3、如何去重？  abca   通过取Max值
    public static int findSubstringInWraproundString(String s) {

        int n = s.length();
        int[] sArr = new int[n];
        for (int i = 0; i < n; i++) {
            sArr[i] = s.charAt(i)-'a';
        }
        int[] dp = new int[26];

        dp[sArr[0]] = 1;
        int len =1;
        for (int i = 1; i < sArr.length; i++) {
            int pre = sArr[i-1];
            int cur = sArr[i];
            if((pre==25&&cur==0)||cur-pre==1){
                //不能用如下 计算如  abcdaade  d位置就不行
                //ans+=dp[pre]+1;
                len++;
            }else{
                len=1;
            }
            dp[cur] = Math.max(dp[cur],len);
        }
        int ans = 0;
        for (int i = 0; i < dp.length; i++) {
            ans+=dp[i];
        }
        return ans;
    }

}
